package jianzhiOffer;

class Node1 {
    public int val;
    public Node1 left;
    public Node1 right;

    public Node1() {}

    public Node1(int _val) {
        val = _val;
    }

    public Node1(int _val,Node1 _left,Node1 _right) {
        val = _val;
        left = _left;
        right = _right;
    }
}
public class Num36 {
    Node1 prev,head;
    public Node1 treeToDoublyList(Node1 root) {
        if(root == null) return null;
        dfs(root);
        head.left = prev;
        prev.right = head;
        return head;
    }
    void dfs(Node1 cur) {
        if(cur == null) return;
        dfs(cur.left);
        if(prev == null) {
            head = cur;
        }else {
            prev.right = cur;
        }
        cur.left = prev;
        prev = cur;
        dfs(cur.right);
    }
}
